package com.eistert.java.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;

/**
 * @Description: 马踏棋盘算法实现代码
 * @Author: ai
 * @create: 2023-04-25 15:12
 */
public class HorseChessboard {
    private static int X; // 棋盘有多少行
    private static int Y; // 棋盘有多少列
    private static boolean[] visited; // 点是否被访问过
    private static boolean finished;


    public HorseChessboard() {
    }

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int column = 1;

        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];

        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();

        System.out.println("共耗时： " + (end - start) + " 毫秒");

        // 输出棋盘的最后情况
//        for (int[] rows : chessboard) {
//            for (int step : rows) {
//                System.out.print(step + "\t");
//            }
//            System.out.println();
//        }
        int[][] var11 = chessboard;
        int var10 = chessboard.length;

        for (int var9 = 0; var9 < var10; ++var9) {
            int[] rows = var11[var9];
            int[] var15 = rows;
            int var14 = rows.length;

            for (int var13 = 0; var13 < var14; ++var13) {
                int step = var15[var13];
                System.out.print(step + "\t");
            }

            System.out.println();
        }


    }


    /**
     * 遍历棋盘
     *
     * @param chessboard 棋盘二维数组
     * @param row        行
     * @param column     列
     * @param step       走的步数
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        // 当前点的坐标置为已访问
        visited[row * X + column] = true;

        // 获取当前节点可以访问的点集合
        ArrayList<Point> ps = next(new Point(column, row));

        sort(ps);

        while (!ps.isEmpty()) {
            Point p = (Point) ps.remove(0);

            if (!visited[p.y * X + p.x]) { // 如果当前点没有被访问过
                // y 代表行，x 代表列
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }

        // 判断马儿是否完成了任务，使用	step 和应该走的步数比较 ，
        // 如果没有达到数量，则表示没有完成任务，将整个棋盘置 0
        // 说明: step < X * Y	成立的情况有两种
        // 1. 棋盘到目前位置,仍然没有走完
        // 2. 棋盘处于一个回溯过程
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;// todo 这一步不懂
        } else {
            finished = true;
        }


    }


    /**
     * 下一步可以走的点
     *
     * @param curPoint 当前的点
     * @return 下一步可以走的点集合
     */
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList();
        Point p1 = new Point();
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }

        return ps;
    }


    /**
     * 按非递减顺序排序 1,2,2,3,4,5,6,6
     *
     * @param ps 下一步可以走的点集合
     */
    public static void sort(ArrayList<Point> ps) {
        ps.sort((o1, o2) -> {
            int count1 = HorseChessboard.next(o1).size();
            int count2 = HorseChessboard.next(o2).size();

            if (count1 < count2) {
                return -1;

            } else {
                return count1 == count2 ? 0 : 1;
            }
        });
    }
}
